"""
题目：在无权图中，计算从起点到终点的最短路径长度（边的数量）。

BFS（广度优先搜索）天然适合求解无权图的最短路径，因为它按 “层次” 遍历，首次到达终点时经过的路径就是最短路径。具体步骤：
BFS 保证 “首次到达终点的路径是最短路径”，因为它按距离起点由近及远的顺序遍历。
时间复杂度 O (V + E)（V 为节点数，E 为边数），效率较高。
"""


class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    def shortest_path_length(self, start, end):
        """使用BFS计算无权图中最短路径长度（边的数量）"""
        # 顶点不存在图上 返回-1
        if start not in self.vertices or end not in self.vertices:
            return -1
        # 起点和终点相同
        if start == end:
            return 0
        #用visited集合避免重复访问顶点，防止因环导致的死循环。
        visited = set()
        queue = [(start, 0)]  #初始化队列，元素为元组(当前顶点, 到该顶点的距离)，初始时起点距离为0 用队列存储 “顶点 + 距离” 的元组，保证遍历的层级顺序。
        visited.add(start)
        # 当队列不为空时，持续进行BFS遍历
        while queue:
            current, distance = queue.pop(0)
            # 遍历邻接顶点
            for neighbor in self.vertices[current]:
                # 若邻接顶点是终点，说明找到最短路径，返回当前距离+1（因为从当前顶点到终点只需一步）
                if neighbor == end:
                    return distance + 1  # 找到终点，返回距离+1   +1是因为你是邻接点，还需要一步才能到达....
                # 若邻接顶点未被访问过
                if neighbor not in visited:
                    visited.add(neighbor)
                    # 将该邻接顶点和对应的距离（当前距离+1）加入队列
                    queue.append((neighbor, distance + 1))  # 距离+1
        # 若队列遍历完毕仍未找到终点，说明起点和终点不连通，返回-1
        return -1  # 不存在路径


# 测试
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 5)

# 从0到5的路径:
# 0->2->5 (长度2)
# 0->1->3->5 (长度3)
# 最短路径长度为2
print(graph.shortest_path_length(0, 5))  # 输出: 2
print(graph.shortest_path_length(0, 6))  # 输出: -1 (6不在图中)
